package done.normal_101_200;

import com.study.common.ListNode;
import org.junit.Test;

import static com.study.common.ListNode.newCycle;
import static com.study.util.LogUtil.info;

/**
 * 142. Linked List Cycle II 环形链表 II
 * <p>
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置
 * （索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 * 说明：不允许修改给定的链表。
 * <p>
 * 示例 1：
 * <p>
 * 3 -> 2 -> 0 -> -4
 * /\         |
 * |_________|
 * <p>
 * 输入：head = [3, 2, 0, -4], pos = 1
 * 输出：tail connects to node index 1
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * 1 -> 2
 * /\   |
 * |____|
 * <p>
 * 输入：head = [1, 2], pos = 0
 * 输出：tail connects to node index 0
 * 解释：链表中有一个环，其尾部连接到第一个节点。
 * <p>
 * 2019-05-22 23:15
 **/
@SuppressWarnings("all")
public class LinkedListCycleII {

    public ListNode detectCycle(ListNode head) {
        // 190522 first
        // 190528 second
        return null;
    }

    @Test
    public void test() {
        info(detectCycle(newCycle(3, 2, 0, -4, 5, 6, 5)).val);
    }
}


















































/*
public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;

    while (slow != null && fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        //快慢指针的处理只能判断是否有环,并不能判断出在哪里出现的环
        if (fast == slow) {

            //循环链表的head  如果head和slow中的某一个节点出现相同
            //代表在链表的该条直线上,出现了环
            while (head != slow) {
                head = head.next;
                slow = slow.next;
            }
            return slow;
        }
    }
    return null;
}
*/